package leetcode;

public class _160 {

	public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

		ListNode _a = headA;
		ListNode _b = headB;

		boolean a2b = false;
		boolean b2a = false;

		if (null == headA && null != headB) {
			return null;
		}
		if (null == headB && null != headA) {
			return null;
		}

		while (_a != _b) {
			_a = _a.next;
			if (null == _a && (!a2b)) {
				_a = headB;
				a2b = true;
			}
			_b = _b.next;
			if (null == _b && (!b2a)) {
				_b = headA;
				b2a = true;
			}
		}
		return _a;
	}

	/**
	 * 3ms
	 * 
	 * @param headA
	 * @param headB
	 * @return
	 */
	public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {

		long lenA = getLength(headA);
		long lenB = getLength(headB);
		if (lenA >= lenB) {
			headA = prepareListNode(headA, lenA - lenB);
		} else {
			headB = prepareListNode(headB, lenB - lenA);
		}
		while (headA != headB) {
			headA = headA.next;
			headB = headB.next;
		}
		return headA;
	}

	private ListNode prepareListNode(ListNode listNode, long delta) {
		long _delta = 0;
		while (_delta != delta) {
			listNode = listNode.next;
			_delta = _delta + 1;
		}
		return listNode;
	}

	private long getLength(ListNode ln) {
		int len = 0;
		while (null != ln) {
			len = len + 1;
			ln = ln.next;
		}
		return len;
	}

}
